package oj_leetcode;

import java.util.Map;
import java.util.TreeMap;

public class DivideTwoIntegers {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean flag; // true +, false -
        flag = dividend > 0 == divisor > 0;
        if (dividend > 0) {
            dividend = -dividend;
        }
        if (divisor > 0) {
            divisor = -divisor;
        }
        int count = 0;
        int acc = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(divisor, 1);
        while (dividend <= acc) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(dividend - acc);
            if (entry == null){
                break;
            }
            acc += entry.getKey();
            count += entry.getValue();
            map.put(acc, count);
        }
        if (flag) {
            return count;
        } else {
            return -count;
        }

    }
}
